package problems.daily;

/**
 * 1620. 网络信号最好的坐标
 * <p>https://leetcode.cn/problems/coordinate-with-maximum-network-quality/</p>
 *
 * @author habitplus
 * @since 21:24, 2022/11/2
 */
public class DT1620 {
    public int[] bestCoordinate(int[][] towers, int radius) {
        if (towers == null || towers.length < 1 || radius < 1) return null;
        int maxX = 0, minX = 51;
        int maxY = 0, minY = 51;

        for (int[] t : towers) {
            minX = Math.min(t[0], minX);
            maxX = Math.max(t[0], maxX);
            minY = Math.min(t[1], minY);
            maxY = Math.max(t[1], maxY);
        }

        int max = 0;
        int sum, dis;
        int[] ret = new int[2];
        radius *= radius;
        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                sum = 0;
                for (int[] t : towers) {
                    dis = distance(x, y, t[0], t[1]);
                    if (dis <= radius) {
                        sum += (int) Math.floor(t[2] / (1 + Math.sqrt(dis)));
                    }
                }

                if (max < sum) {
                    max = sum;
                    ret[0] = x;
                    ret[1] = y;
                }
            }
        }

        return ret;
    }

    private int distance(int ax, int ay, int bx, int by) {
        return (ax - bx) * (ax - bx) + (ay - by) * (ay - by);
    }
}
